package com.eddie.tree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import lombok.Setter;

import java.io.Serializable;
import java.util.List;
import java.util.function.Function;

/**
 * @author Eddie
 * @date 2022/08/09 11:41
 **/
public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        //创建节点
        HeroNode root = new HeroNode(1, "Eddie");
        HeroNode ironMan = new HeroNode(2, "Iron Man");
        HeroNode tom = new HeroNode(3, "Tom");
        HeroNode hongKong = new HeroNode(4, "HongKong");
        HeroNode doll = new HeroNode(5, "Doll");
        //说明：先手动创建二叉树，后面学习递归的方式创建二叉树
        root.setLeft(ironMan);
        root.setRight(tom);
        tom.setRight(hongKong);
        tom.setLeft(doll);
        int x = 1;
        int y = 1;
        System.out.println(x++ * x + y++);
        binaryTree.setRoot(root);
//        binaryTree.preOrder();
//        System.out.println("中序遍历");
//        binaryTree.infixOrder();
//        System.out.println("后序遍历");
        System.out.println("删除前~~~~");
        binaryTree.postOrder();

//        binaryTree.infixOrderSearch(4);
        FunctionInterface<User> functionInterface = user -> user;
        User eddie = functionInterface.test(new User("Eddie", 12));
        System.out.println(eddie);

        binaryTree.delHeroNode(3);
        System.out.println("删除后");
        ;
        binaryTree.postOrder();
    }
}

@Data
@AllArgsConstructor
@NoArgsConstructor
class User implements Serializable{
    private String nickName;
    private Integer age;
}

@FunctionalInterface
interface FunctionInterface<T extends Serializable >{
        T test(T data);
        }


/**
 * 创建二叉树
 */
class BinaryTree {
    @Setter
    private HeroNode root;

    //前序遍历
    public void preOrder() {
        if (isEmpty()) {
            System.out.println("二叉树为空，无法遍历");
            return;
        }
        root.preOrder();
    }

    /**
     * //中序遍历
     */
    public void infixOrder() {
        if (isEmpty()) {
            System.out.println("二叉树为空，无法遍历");
            return;
        }
        root.infixOrder();
    }

    //后续遍历
    public void postOrder() {
        if (isEmpty()) {
            System.out.println("二叉树为空，无法遍历");
            return;
        }
        root.postOrder();
    }

    public void infixOrderSearch(int id) {
        if (!isEmpty()) {
            System.out.println(root.infixOrderSearch(id));
            System.out.println("查找的次数为：" + HeroNode.count);
        }
    }

    public void postOrderSearch(int id) {
        if (!isEmpty()) {
            System.out.println(root.postOrderSearch(id));
            System.out.println("查找的次数为：" + HeroNode.count);
        }
    }

    public void preOrderSearch(int id) {
        if (!isEmpty()) {
            System.out.println(root.preOrderSearch(id));
            System.out.println("查找的次数为：" + HeroNode.count);
        }
    }

    public void delHeroNode(int id) {
        if (!isEmpty()) {
            if (root.getNo() == id) {
                root = null;
            } else {
                root.delHeroNode(id);
            }
        } else {
            System.out.println("树为空");
        }
    }

    boolean isEmpty() {
        return this.root == null;
    }
}

/**
 * 创建HeroNode节点
 */
@Data
class HeroNode {
    private int no;
    private String name;
    private HeroNode left; //默认null
    private HeroNode right;//默认null

    public static int count;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    /**
     * 编写前序遍历方法
     */
    public void preOrder() {
        //先输出父节点
        System.out.println(this);
        //递归向左前序遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        //递归向右前序遍历
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        //输出父节点
        System.out.println(this);
        //递归向右中序遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    public HeroNode preOrderSearch(int id) {
        count++;

        //先输出父节点
        if (id == this.no) {
            return this;
        }
        //1.判断当前节点的左子节点是否为空，如果不为空，则递归向左查找
        //2.如果左递归谦虚查找，找到节点返回
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(id);
        }

        //说明在左子树找到了
        if (resNode != null) {
            return resNode;
        }
        //递归向右前序查找
        if (this.right != null) {
            resNode = this.right.preOrderSearch(id);
        }

        //直接返回结果，尽管没找到
        return resNode;
    }

    public HeroNode infixOrderSearch(int id) {
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(id);
        }
        if (resNode != null) {
            return resNode;
        } else if (this.no == id) {
            count++;
            return this;
        }

        if (this.right != null) {
            resNode = this.right.infixOrderSearch(id);
        }
        return resNode;
    }

    public HeroNode postOrderSearch(int id) {
        HeroNode heroNode = null;
        if (this.left != null) {
            heroNode = this.left.postOrderSearch(id);
        }
        if (heroNode != null) {
            return heroNode;
        }
        if (this.right != null) {
            heroNode = this.right.postOrderSearch(id);
        }

        if (heroNode != null) {
            return heroNode;
        }
        count++;
        if (this.no == id) {
            return this;
        }
        return heroNode;
    }

    public void delHeroNode(int id) {
        //思路:
        /*
         1、因为二叉树是单向的，所以判断当前节点的子节点是否是要删除的，不能判断当前节点
         2、如果当前节点的左子节点不为空，并且就是要删除的节点，就将this.left =null;并且就返回（结束递归删除）
         3、如果当前节点的右子节点不为空，并且就是要删除的节点，就将this.right =null;并且就返回（结束递归删除）
         4、如果第二和第三部没有删除节点，那么需要向左子树进行递归
         5、如果第四部‍没有删除节点，那么需要向右 子树进行递归
         */
        if (this.left != null && this.left.no == id) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == id) {
            this.right = null;
            return;
        }
        //向左子树递归删除
        if (this.left != null) {
            this.left.delHeroNode(id);
        }

        //向左子树递归删除
        if (this.right != null) {
            this.right.delHeroNode(id);
        }
    }

    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

}